﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using LogicalComponent.util;

namespace LogicalComponent.rules.grid
{
    /// <summary>
    /// Base class for Dijkstra type algorithms.  This abstract class can be used for AStar searches by 
    /// a non-zero admisable hueristic on the grid.
    /// </summary>
    public abstract class SearchAlgorithm
    {
        protected Coordinate source;
        protected SortedList<Fraction, Coordinate> exposed;
        protected HashSet<Coordinate> visited;
        protected Hashtable exposedData;
        protected Fraction cost;
        protected MoveRuleSet moveRules;

        /// <summary>
        /// Gets the hueristic.
        /// </summary>
        /// <param name="c">The coordinate.</param>
        /// <returns></returns>
        protected abstract Fraction GetHueristic(Coordinate c);
        /// <summary>
        /// Determines whether this instance is done.
        /// </summary>
        /// <returns>
        ///   <c>true</c> if this instance is done; otherwise, <c>false</c>.
        /// </returns>
        protected abstract bool IsDone();

        /// <summary>
        /// Initializes a new instance of the <see cref="AStarGrid&lt;G, T&gt;.DijkstraBase"/> class.
        /// </summary>
        /// <param name="moveRules">The moveRules.</param>
        /// <param name="source">The source.</param>
        public SearchAlgorithm(MoveRuleSet moveRules, Coordinate source)
        {
            this.moveRules = moveRules;
            this.source = source;
            this.exposed = new SortedList<Fraction,Coordinate>();
            this.visited = new HashSet<Coordinate>();
            this.exposedData = new Hashtable();
            this.cost = new Fraction(0);
        }

        /// <summary>
        /// Does the search on this Algorithm
        /// </summary>
        public void DoSearch()
        {
            Coordinate next = this.source;
            this.exposedData.Add(this.source, new SearchEntry(cost, null));

            while (true)
            {
                if (this.IsDone()){ break; }
                if (!this.visited.Contains(next))
                {
                    this.visit(next, this.cost);
                }

                if (this.exposed.Count == 0)
                {
                    return;
                }

                next = exposed.Values[0];
                this.cost = ((SearchEntry)exposedData[next]).Item1;
                exposed.RemoveAt(0);
            }
        }

        /// <summary>
        /// Gets the path to a destination, will only work after DoSearch is complete.
        /// </summary>
        /// <param name="destination">The destination.</param>
        /// <returns>The path to the destination given</returns>
        public Path GetPathTo(Coordinate destination)
        {
            if (!this.visited.Contains(destination))
            {
                return null;
            }

            Coordinate next = destination;
            List<Coordinate> traceBack = new List<Coordinate>();
            while (true)
            {
                traceBack.Add(next);
                if (next == source) {break;}
                next = ((SearchEntry)exposedData[next]).Item2;
            }
            traceBack.Reverse();

            Path path = new Path(this.source);
            path.Cost = ((SearchEntry)exposedData[destination]).Item1;
            foreach (Coordinate coordinate in traceBack)
            {
                if (coordinate != this.source)
                {
                    path.AddCoordinate(coordinate);
                }
            }
            return path;
        }

        /// <summary>
        /// Get the coordinates visited by this algorithm.
        /// </summary>
        /// <returns>List of the coordinates visited by this algorithm</returns>
        public List<Coordinate> GetVisited()
        {
            return this.visited.ToList();
        }

        /// <summary>
        /// Return whether or not the given coordinate was visited.
        /// </summary>
        /// <param name="c">The coordinate to check.</param>
        /// <returns>true if the coordinate was visited by the algorithm, false otherwise</returns>
        public bool WasVisited(Coordinate c)
        {
            return this.visited.Contains(c);
        }

        /// <summary>
        /// Visits the specified source.
        /// </summary>
        /// <param name="source">The source.</param>
        /// <param name="cost">The cost.</param>
        private void visit(Coordinate tovisit, Fraction cost)
        {
            this.visited.Add(tovisit);
            Coordinate[] neighbors = this.moveRules.GetNeighbors(tovisit);

            for (int i = 0; i < neighbors.Count(); i++)
            {
                Coordinate c = neighbors[i];

                if (this.moveRules.Grid.IsOnGrid(c))
                {
                    Fraction addedCost = this.moveRules.GetCost(tovisit, c);

                    if (addedCost >= 0 && this.ExposedNeedsUpdate(c, cost + addedCost))
                    {
                        this.Expose(c, cost + addedCost, tovisit);
                    }
                }
            }
        }

        /// <summary>
        /// Exposes the specified coordinate, calculating its hueristic and distanc to it.
        /// </summary>
        /// <param name="toExpose">To expose.</param>
        /// <param name="cost">The cost.</param>
        /// <param name="source">The source.</param>
        protected virtual void Expose(Coordinate toExpose, Fraction cost, Coordinate from)
        {
            this.exposed.Add(cost + this.GetHueristic(toExpose), toExpose);
            SearchEntry entry = new SearchEntry(cost, from);
            if (this.exposedData.ContainsKey(toExpose))
            { 
                this.exposedData.Remove(toExpose); 
            }
            this.exposedData.Add(toExpose, entry);
        }

        protected bool ExposedNeedsUpdate(Coordinate toExpose, Fraction cost)
        {
            if (!this.moveRules.Grid.IsOnGrid(toExpose))
            {
                return false;
            }
            if (this.exposedData.ContainsKey(toExpose))
            {
                Fraction oldCost = ((SearchEntry)exposedData[toExpose]).Item1;
                return cost < oldCost;
            }
            return true;
        }
    }

    /// <summary>
    /// Class that hold the data and perform the algorithm for finding teh cheapest path
    /// from a source to a destination.
    /// </summary>
    public class AStarSearch : SearchAlgorithm
    {
        Coordinate destination;

        /// <summary>
        /// Initializes a new instance of the <see cref="AStarSearch"/> class.
        /// </summary>
        /// <param name="moveRules">The move rules.</param>
        /// <param name="source">The source.</param>
        /// <param name="destination">The destination.</param>
        public AStarSearch(MoveRuleSet moveRules, Coordinate source, Coordinate destination) : base(moveRules, source)
        {
            this.destination = destination;
        }

        protected override Fraction GetHueristic(Coordinate c)
        {
            return this.moveRules.GetHueristic(this.source, this.destination);
        }

        protected override bool IsDone()
        {
            return this.visited.Contains(this.destination);
        }
    }

    /// <summary>
    /// Class that hold the data and perform the algorithm for finding teh cheapest path
    /// from a source to a destination.
    /// </summary>
    public class DijkstraFlood : SearchAlgorithm
    {
        private Fraction maxCost;
        private HashSet<Coordinate> withoutFullCost;

        /// <summary>
        /// Initializes a new instance of the <see cref="DijkstraFlood"/> class.
        /// </summary>
        /// <param name="moveRules">The move rules.</param>
        /// <param name="source">The source.</param>
        /// <param name="maxCost">The max cost.</param>
        public DijkstraFlood(MoveRuleSet moveRules, Coordinate source, Fraction maxCost) : base(moveRules, source)
        {
            this.maxCost = maxCost;
            this.withoutFullCost = new HashSet<Coordinate>();
        }

        protected override Fraction GetHueristic(Coordinate c)
        {
            return new Fraction(0);
        }

        protected override bool IsDone()
        {
            bool isDone = this.maxCost < this.cost;
            if (isDone && !this.moveRules.NeedsFullCost)
            {
                foreach (Coordinate c in this.withoutFullCost)
                {
                    this.visited.Add(c);
                }
            }
            return isDone;
        }

        protected override void Expose(Coordinate toExpose, Fraction cost, Coordinate from)
        {
            Fraction fromCost = ((SearchEntry)this.exposedData[from]).Item1;
            if (fromCost < maxCost && cost > maxCost)
            {
                this.withoutFullCost.Add(toExpose);
            }
            else if (this.withoutFullCost.Contains(toExpose))
            {
                this.withoutFullCost.Remove(toExpose);
            }
            base.Expose(toExpose, cost, from);
        }
    }

    /// <summary>
    /// Data class, Unity does not suport tuples, so this had to suffice for holding data about
    /// the estimated cost from a given tile.
    /// </summary>
    public class SearchEntry
    {
        public Fraction Item1 { get; set; }
        public Coordinate Item2 { get; set; }

        /// <summary>
        /// Initializes a new instance of the <see cref="SearchEntry"/> class.
        /// </summary>
        /// <param name="item1">The item1.</param>
        /// <param name="item2">The item2.</param>
        public SearchEntry(Fraction item1, Coordinate item2)
        {
            this.Item1 = item1;
            this.Item2 = item2;
        }
    }
}
